package java学习.leetcode.editor.cn.数组;

/**
 * @author 刘世锦
 * 2022-09-27 09:26:50	 当前时间
 */
//给定一个含有 n 个正整数的数组和一个正整数 target 。 
//
// 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长
//度。如果不存在符合条件的子数组，返回 0 。 
//
// 
//
// 示例 1： 
//                                 j
//                             i
//输入：target = 7, nums = [2,3,1,2,4,3]
//输出：2
//解释：子数组 [4,3] 是该条件下的长度最小的子数组。
// 
//
// 示例 2： 
//
// 
//输入：target = 4, nums = [1,4,4]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：target = 11, nums = [1,1,1,1,1,1,1,1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target <= 109 
// 1 <= nums.length <= 105 
// 1 <= nums[i] <= 105 
// 
//
// 
//
// 进阶： 
//
// 
// 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 
// 
// Related Topics 数组 二分查找 前缀和 滑动窗口 
// 👍 1387 👎 0

public class 长度最小的子数组{
	public static void main(String[] args) {
		Solution solution = new 长度最小的子数组().new Solution();
		int target = 7;
		int[] nums = {2,3,1,2,4,3};
		System.out.println(solution.minSubArrayLen(target,nums));
		System.out.println(solution.minSubArrayLen1(target,nums));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//		暴力
    public int minSubArrayLen1(int target, int[] nums) {
		//输入：target = 7, nums = [2,3,1,2,4,3]
		//输出：2
		//解释：子数组 [4,3] 是该条件下的长度最小的子数组。
		/** j→
		 *  i
		 *  0 1 2 3 4 5
		 * [2,3,1,2,4,3 ]
		 */
		int  l = 0;
		int res = 100000;
		for (int i = 0; i < nums.length; i++) {
			int cur=0;
			for (int j = i; j < nums.length; j++) {
//				确定了i之后，j以i为起点，j开始向右遍历，累加，直到超过target，取最小值
//				随后从下一个i开始
				cur+=nums[j];
				 if (cur>=target){
					 l = j-i+1;
					res = Math.min(res,l);
					break;
				}
			}
		}
		return res==100000?0:res;
    }

	/***
	 * 双指针：
	 * 每次求得 sum+=nums[j],
	 * 若 sum<target : 继续累加
	 * 若 sum>=target: 此时已满足条件，i-- 试图求最小长度。
	 */
	public int minSubArrayLen(int target, int[] nums) {
		/**       j→
		 *  i
		 *  0 1 2 3 4 5
		 * [2,3,1,2,4,3 ]
		 */
		int i=0,j=0;
		int len = Integer.MAX_VALUE;
		int sum = 0;
		while ( j<nums.length){

				sum+=nums[j];
				j++;
//            只要大于target,一直缩小
				while (sum>=target){
					sum-=nums[i];
					i++;
					len = Math.min(len,j-i+1);

				}
		}
		return len==Integer.MAX_VALUE?0:len;
	}
	public int minSubArrayLen3(int target, int[] nums) {
    	int sum = 0;
    	int len = nums.length+1,i=0;
		for (int j = 0; j < nums.length; j++) {
			sum+=nums[j];
			while (sum>=target){
				len = Math.min(len,j-i+1);
				sum-=nums[i];
				i++;
			}
		}
		return len == nums.length+1?0:len;
	}
	}
//leetcode submit region end(Prohibit modification and deletion)

}
